#include <iostream>
#include <memory>   // 用于 std::allocator 和 std::uninitialized_copy
using std::cout;
using std::endl;
using std::allocator;
//using std::construct;
using std::uninitialized_copy;

template<typename T>
class Vector{ 
public:     
    Vector();     
    ~Vector();          
    void push_back(const T &);      
    void pop_back();         
    int size();     
    int capacity(); 
    void display();
private:
    //void* allocate(size_t);   // 使用allocator
    //void* reallocate();       // 重新分配内存,动态扩容要用的
    void reallocate();         // push_back不需要返回地址，因此不使用void*
    void deallocate();
private:         
    static std::allocator<T> _alloc;    // 静态分配器实例          
    T *_start;                 // 指向数组中的第一个元素     
    T *_finish;                // 指向最后一个实际元素之后的那个元素     
    T *_end_of_storage;        // 指向数组本身之后的位置 
};

// 静态成员初始化
template<typename T>
allocator<T> Vector<T>::_alloc;

// 在定义模板类的成员函数时，必须加上template<typename T>，并且类名要写成vector<T>
template<typename T>
Vector<T>::Vector()
    :_start(nullptr)
    ,_finish(nullptr)
    ,_end_of_storage(nullptr){
}     

template<typename T>
Vector<T>::~Vector(){
    deallocate();
}          

template<typename T>
void Vector<T>::push_back(const T& value){
    if(_finish == _end_of_storage){
        reallocate();
    }

    _alloc.construct(_finish++, value);  // 在已分配的内存(ptr)上构造一个T类型对象，传递args给构造函数
}   

template<typename T>
void Vector<T>::pop_back(){
    if(_start == _finish){
        return;
    }

//    _alloc.destruct(--_finish);
    _alloc.destroy(--_finish);  // 正确析构对象，而不仅仅是清空内存，会同时调用~T()

//    if(_start == _finish){
//        return;
//    }
}         

template<typename T>
int Vector<T>::size(){
    // 指针的减法运算会自动计算的是元素个数，而不是字节数
    return _finish - _start;
}     

template<typename T>
int Vector<T>::capacity(){
    return _end_of_storage - _start;
} 
    
template<typename T>
void Vector<T>::display(){
    for(T* it = _start; it != _finish; ++it){
        cout << *it << " ";
    }
    cout << endl;
}

#if 0
// malloc分配的内存无法与allocator.deallocate配合
template<typename T>
void* Vector<T>::allocate(size_t n){
    void* result = malloc(n);
    if(result == 0) return nullptr;
    return result;
}
#endif

template<typename T>
//void* Vector<T>::reallocate(){
void Vector<T>::reallocate(){
    size_t cur_size = size();
    
    # if 0
    if(cur_size == 0){
        size_t new_size = 1;
        //void* result = _alloc.construct(new_size);    // 可变参数，第一个是类型
        _alloc.allocate(new_size);  // 后面一定要处理三个指针，否则会core dump
    }else{
        #if 0
        size_t new_size = 2 * cur_size;
        void* result = allocate(new_size);
        if(result == 0) return nullptr;
        
        //copy(_start, _finish, result);
        uninitialized_copy(_start, _finish, result);
        void* temp = _start;

        _start = result;
        _finish = _start + cur_size;
        _end_of_storage = _start + new_size;

        deallocate(temp);
        #endif

        size_t new_size = 2 * cur_size;
    }
    # endif
        size_t new_size = (cur_size == 0 ? 1 : 2 * cur_size);    

        T* new_start = _alloc.allocate(new_size);
        T* new_finish = uninitialized_copy(_start, _finish, new_start);    // 可以使用未初始化的内存

        deallocate();
        
        _start = new_start;
        _finish = new_finish;
        _end_of_storage = _start + new_size;

}

template<typename T>
void Vector<T>::deallocate(){
    // free(_start);    // free接收void*，而_start是T*
    if(_start){
        for(T* p = _start; p != _finish; ++p){
            _alloc.destroy(p);
        }

        _alloc.deallocate(_start, _end_of_storage - _start);

        _start = _finish = _end_of_storage = nullptr;
    }
}

void test(){
    // Vector vec; // Vector是模板，需要指定T
    Vector<int> vec;
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);
    vec.display();
    vec.pop_back();
    vec.display();
}

int main()
{
    test();
    return 0;
}

